﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace WindowsFormsApplication1
{
    class TSP
    {
        static int REPEAT_COUNT = 1;
        static double INITIAL_TEMPERATURE = 400.0;
        static int COOLING_STEPS		= 500;
        static double COOLING_FRACTION = 0.999;
        static int STEPS_PER_TEMP		= 1000	;
        static double E = Math.E;
        static double K = 0.01;


        public delegate void DrawDelagete(int timeout);

        public struct DataFromFile
        {
            public string name;
            public string type;
            public string comment;
            public int dimension;
            public string EDGE_WEIGHT_TYPE;
            public string EDGE_WEIGHT_FORMAT; 
            public double[,] matrix;
        }

        public static string GetValue(string keyAndValue, string key)
        {
            return keyAndValue.Substring(key.Length, keyAndValue.Length - key.Length);
        }
        public static string GetFirstWord(string input)
        {
            int index = 0;
            while (input[index++] == ' ' && index < input.Length) ;
            int start = index;
            while (input[index++] != ' ' && index < input.Length) ;
            return input.Substring(start - 1, index - start + 1);
        }
        public static DataFromFile ReadFromFile(string filePath)
        {
            DataFromFile result = new DataFromFile();

            FileStream fileStream = new FileStream(filePath, FileMode.Open, FileAccess.Read);
            StreamReader reader = new StreamReader(fileStream);

            string entireFile = reader.ReadToEnd();

            reader.Close();
            fileStream.Close();

            string[] splited = entireFile.Split('\n');
            result.name = GetValue(splited[0], "NAME:");
            result.type = GetValue(splited[1], "TYPE:");
            result.comment = GetValue(splited[2], "COMMENT:");

            string dimensionsStringWithSpaces = GetValue(splited[3], "DIMENSION:");
            string dimensionsString = GetFirstWord(dimensionsStringWithSpaces);
            int n = result.dimension = int.Parse(dimensionsString);

            double[,] elements = new double[n, n];
            int elementsCount = 0;

            for (int i = 7; i < splited.Length; ++i)
            {
                string[] digitsonly = splited[i].Split(' ');
                for (int j = 0; j < digitsonly.Length; ++j)
                {
                    string good = digitsonly[j].Replace('.', ',').Replace('\r', '\0').Replace('\n', '\0');
                    if (good != "")
                    {
                        elements[elementsCount / n, elementsCount % n] = double.Parse(good);
                        ++elementsCount;
                    }
                    if (elementsCount == n * n)
                        break;
                }
                if (elementsCount == n * n)
                    break;
            }

            result.matrix = elements;
            return result;
        }

        public static void InitializeSolution(DataFromFile data, int[] solution)
        {
            for (int i = 0; i < data.dimension; ++i)
            {
                solution[i] = i;
            }
        }

        public static void RandomSolution(int[] solution)
        {
            Random r = new Random();
            for (int i = solution.Length - 1; i > 0; --i)
            {
                int firstIndex = r.Next(0, i);
                int tmp = solution[firstIndex];
                solution[firstIndex] = solution[i];
                solution[i] = tmp; ;
            }
        }

        public static double SolutionCoast(DataFromFile data, int[] solution)
        {
            double result = 0;

            for (int i = 0; i < solution.Length - 1; ++i)
            {
                result += data.matrix[solution[i], solution[i + 1]];
            }

            result += data.matrix[solution[0], solution[solution.Length - 1]];

            return result;
        }

        public static double Transition(DataFromFile data, int[] solution, int i, int j)
        {
            double was, willbe;
            bool neighbors = false;
            if (i == j)
                return 0;

            if (i > j)
                return Transition(data, solution, j, i);

            if (i == (j - 1)) neighbors = true;

            if ((i == 1) && (j == (solution.Length)))
            {
                int tmp = i;
                i = j;
                j = tmp;
                neighbors = true;
            }

            //if (neighbors)
            //{
            //    was = data.matrix[solution[i - 1], solution[i]] + data.matrix[solution[j], solution[j + 1]];
            //}
            //else
            //{
            //    was = data.matrix[solution[i - 1], solution[i]] + data.matrix[solution[i], solution[i + 1]]
            //        + data.matrix[solution[j - 1], solution[j]] + data.matrix[solution[j], solution[j + 1]];
            //}

            was = SolutionCoast(data, solution);

            int tmp1 = solution[i];
            solution[i] = solution[j];
            solution[j] = tmp1;

            willbe = SolutionCoast(data, solution);
            //if (neighbors)
            //{
            //    willbe = data.matrix[solution[i - 1], solution[i]] + data.matrix[solution[j], solution[j + 1]];
            //}
            //else
            //{
            //    willbe = data.matrix[solution[i - 1], solution[i]] + data.matrix[solution[i], solution[i + 1]]
            //        + data.matrix[solution[j - 1], solution[j]] + data.matrix[solution[j], solution[j + 1]];
            //}

            return (willbe - was);
        }

        public static void HillClimbing(DataFromFile data, int[] solution, DrawDelagete DrawMethod, int timeout)
        {
            double coast;
            double deltha;
            bool stuck;
            double transition;
            InitializeSolution(data, solution);
            RandomSolution(solution);
            coast = SolutionCoast(data, solution);
            do
            {
                stuck = true;
                for (int i = 1; i < solution.Length - 1; ++i)
                {
                    for (int j = i + 1; j < solution.Length - 1; ++j)
                    {
                        deltha = Transition(data, solution, i, j);
                        if (deltha < 0)
                        {
                            stuck = false;
                            DrawMethod(timeout);
                            coast += deltha;
                        }
                        else
                        {
                            Transition(data, solution, j, i);
                        }
                    }
                }
            } while (!stuck);
        }

        public static void CopySolution(int[] src, int[] dest)
        {
            for (int i = 0; i < src.Length; ++i)
            {
                dest[i] = src[i];
            }
        }

        public static void MutlistartHillClimbing(DataFromFile data, int[] bestSolution, int samplesCount, DrawDelagete DrawMethod, int timeout)
        {
            int[] solution = new int[bestSolution.Length];
            double beastCoast;
            double costNow = 0;

            InitializeSolution(data, solution);
            beastCoast = SolutionCoast(data, solution);
            CopySolution(solution, bestSolution);

            for (int i = 1; i <= samplesCount; ++i)
            {
                HillClimbing(data, solution, DrawMethod, timeout);
                costNow = SolutionCoast(data, solution);
                if (costNow < beastCoast)
                {
                    beastCoast = costNow;
                    CopySolution(solution, bestSolution);
                }
            }
            DrawMethod(timeout);
        }

        public static void Anneal(DataFromFile data, int[] solution, DrawDelagete DrawMethod, int timeout)
        {
            double proba;
            double alpha = 0.97;
            double temperature = 100.0;
            double epsilon = 0.001;
            double delta;
            double distance = SolutionCoast(data, solution);

            InitializeSolution(data, solution);
            Random r = new Random();

            while (temperature > epsilon)
            {

                int i1 = r.Next(1, solution.Length - 1);
                int i2 = r.Next(1, solution.Length - 1);
                delta = Transition(data, solution, i1, i2);
                if (delta < 0)
                {
                    distance += delta;
                    DrawMethod(timeout);
                }
                else
                {
                    proba = r.Next();
                    if (proba < Math.Exp(-delta / temperature))
                    {
                        distance += delta;
                        DrawMethod(timeout);
                    }
                    else
                    {
                        Transition(data, solution, i1, i2);
                    }
                }
                temperature *= alpha;
            }
        }

        public static void MultiStartAnneling(DataFromFile data, int[] bestSolution, int samplesCount, DrawDelagete DrawMethod, int timeout)
        {
            int[] solution = new int[bestSolution.Length];
            double bestCost;
            double costNow;

            InitializeSolution(data, solution);
            bestCost = SolutionCoast(data, solution);
            CopySolution(solution, bestSolution);
            for (int i = 1; i <= samplesCount; ++i)
            {
                Anneal(data, solution, DrawMethod, timeout);
                costNow = SolutionCoast(data, solution);
                if (costNow < bestCost)
                {
                    bestCost = costNow;
                    CopySolution(solution, bestSolution);
                    DrawMethod(timeout);
                }
            }
        }
    }
}
